package mysql8学习.高级.第06章_索引的数据结构;

/**
 * 3二叉搜索树
 * 如果我们利用二叉树作为索引结构，那么磁盘的I/O次数和索引树的高度是相关的。
 *    ①.二叉搜索树的特点
 *      ●一个节点只能有两个子节点，也就是一个节点度不能超过2
 *      ● 左子节点<本节点;   右子节点>=本节点，  比我大的向右，比我小的向左
 *    ②.查找规则
 *     我们先来看下最基础的二叉搜索树(Binary Search Tree)，
 *     搜索某个节点和插入节点的规则一样，我们假设搜索插入的数值为key:
 *        1.如果key大于根节点，则在右子树中进行查找;
 *        2.如果key小于根节点，则在左子树中进行查找;
 *        3.如果key等于根节点，也就是找到了这个节点，返回根节点即可。
 *
 *    为了提高查询效率,就需要减少磁盘I/O数。
 *    为了减少磁盘I/O的次数,就需要尽量降低树的高度，
 *    需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。
 *    如果运气不好   退化成链表  引出了AVL数
 *
 */
public class J3_二叉搜索树 {
}
